template <typename Comparable>
class SplayTree
{
private:
    struct BinaryNode
    {
        /*二叉查找树节点代码*/
    };
    BinaryNode* root;
    BinaryNode* nullNode;

    void rotateWithLeftChild(BinaryNode*& k2)
    void rotateWithRightChild(BinaryNode*& k1)
    void splay(const Comparable & x, BinaryNode*& t)
    {
        BinaryNode *leftTreeMax, *rightTreeMax;
        static BinaryNode header;

        header.left = header.right = nullNode;
        leftTreeMax = rightTreeMin = &header;

        nullNode->element = x; //保证比较时匹配

        // 除非break，否则一直循环下去
        for(;;)
        {
            if(x<t->element)
            {
                if(x < t->left->element)
                    rotateWithLeftChild(t);
                if(t->left == nullNode)
                    break;
                //连接右侧
                rightTreeMin->left = t;
                rightTreeMin = t;
                t = t->left;
            }
            else if(t->element < x)
            {
                if(t->right->element < x)
                    rotateWithRightChild(t);
                if(t->right == nullNode)
                    break;
                //连接左侧
                leftTreeMax->right = t;
                leftTreeMax = t;
                t = t->right;
            }
            else
                break;
        }
        
        leftTreeMax->right = t->left;
        rightTreeMin->left = t->right;
        t->left = header.right;
        t->right = header.left;
    }
    void insert(const Comparable & x)
    {
        static BinaryNode *newNode = nullptr;

        if(newNode == nullptr)
            newNode = new BinaryNode;
        newNode->element = x;

        if(root == nullNode)
        {
            newNode->left = newNode->right = nullNode;
            root = newNode;
        }
        else
        {
            splay(x,root);
            if(x<root->left)
            {
                newNode->left = root->left;
                newNode->right = root;
                root->left = nullNode;
                root = newNode;
            }
            else if(root->element < x)
            {
                newNode->right = root->right;
                newNode->left = root;
                root->right = nullNode;
                root=  newNode;
            }
            else
                return;
        }
        newNode = nullptr;  //下一次插入将调用new
    }
    void remove(const Comparable & x)
    {
        if(!contains(x))
            return; //没找到该项，什么也不做
        
        // 若找到，则通过contains项根处展开
        BinaryNode *newNode;
        if(root->left == nullNode)
            newTree = root->right;
        else
        {
            //找到左子树最大值，向根节点展开，然后附接上右儿子
            newTree = root->left;
            splay(x,newTree);
            newTree->right = root->right;
        }
        delete root;
        root = newTree;
    }

public:
    SplayTree()
    {
        nullNode = new BinaryNode;
        nullNode->left = nullNode->right = nullNode;
        root = nullNode;
    }
    ~SplayTree()
    {
        makeEmpty();
        delete nullNode;
    }
    /*与二分查找树相同的方法（赋值重载、含参构造函数）*/
};
